#include <stdio.h>
#include <stdlib.h>
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
#define MAX_SIZE 1000
int cmp(const void *a,const void *b){
    int x=*(const int*)a,y=*(const int*)b;
    if( x < y)
        return -1;
    else if( x > y )
        return 1;
    else
        return 0;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    int *retArr[MAX_SIZE];
    int retc=0;
    qsort(nums,numsSize,sizeof(int),cmp);
    for(int i=0; i<=numsSize-3; i++ ){
        if( i>0 && nums[i]==nums[i-1] )
            continue;
        int pleft,pright;
        pleft=i+1,pright=numsSize-1;
        while( pleft < pright ){
            if( pleft>i+1 && nums[pleft]==nums[pleft-1] ){
                pleft++;
                continue;
            }
            if( pright<numsSize-1 && nums[pright]==nums[pright+1] ){
                pright--;
                continue;
            }
            if( nums[pleft]+nums[pright] == -nums[i] ){
                retArr[retc]=malloc(sizeof(int)*3);
                retArr[retc][0]=nums[i];
                retArr[retc][1]=nums[pleft];
                retArr[retc][2]=nums[pright];
                pleft++;
                pright--;
                retc++;
            }else if( nums[pleft]+nums[pright] < -nums[i] ){
                pleft++;
            }else
                pright--;
        }
    }
    *returnSize=retc;
    int **r=malloc(sizeof(int*)*retc);
    *returnColumnSizes=malloc(sizeof(int*)*retc);
    for(int i=0; i<retc; i++ ){
        r[i]=retArr[i];
        (*returnColumnSizes)[i]=3;
    }
    return r;
}

void _3Sum(int *nums , int numsSize){
    for(int i=0;i<numsSize;++i){
        for(int j=i+1;j<numsSize;++j){
            for(int k=j+1;k<numsSize;++k){
                if( nums[i]+nums[j]+nums[k] == 0 )
                    printf("%d %d %d\n",nums[i],nums[j],nums[k]);
            }
        }
    }
    return;
}

int main(){
    int a[]={-1,0,1,2,-1,-4};
    //int a[]={0,0,0};
    //_3Sum(a,sizeof(a)/sizeof(int));
    int retSize;
    int *retCS;
    int **r=threeSum(a, sizeof(a)/sizeof(int), &retSize, &retCS);
    printf("%d\n",retSize);
    for(int i=0; i<retSize; i++){
        for(int j=0; j< retCS[i]; j++)
            printf("%d ",r[i][j]);
        printf("\n");
    }
    return 0;
}
